Date: Thu, 07 Nov 1996 19:09:17 GMT
Server: NCSA/1.5
Content-type: text/html
Last-modified: Mon, 30 Oct 1995 22:12:00 GMT
Content-length: 2811

<HTML>
<HEAD>
<TITLE> Home Page of Deborah A. Joseph </TITLE>
</HEAD>

<BODY>

<H1> <!WA0><IMG ALIGN=MIDDLE SRC="http://www.cs.wisc.edu/~pubs/faculty-info/joseph.gif">
 Deborah A. Joseph </H1>

<BLOCKQUOTE>
 Associate Professor of Computer Sciences and Mathematics <BR>
 <BR>
 Computer Sciences Department <BR>
 University of Wisconsin <BR>
 1210 W. Dayton St. <BR>
 Madison, WI 53706-1685 <BR>
 <BR>
 telephone: (608) 262-1204 <BR>
 fax: (608) 262-9777 <BR>
 email: <!WA1><A HREF="mailto:joseph@cs.wisc.edu">
 joseph@cs.wisc.edu</A> <BR>
</BLOCKQUOTE>

<EM>Ph.D., Purdue University, 1981</EM> <BR>
<EM>Interests:</EM>
Structural and applied complexity theory, computational biology,
computational geometry, mathematical logic <P>

<HR>

<H2> Research Summary </H2>

My research concerns two areas of theoretical computer science:
1) the study of structural properties of complexity classes, and
2) the design and analysis of algorithms for biological problems.
<P>

In the last twenty years a great deal of work has gone into studying
the properties of sets that are decidable in deterministic and
nondeterministic polynomial time. Despite this effort we still
know very little about these classes. Recently in fact some computer
scientists have questioned the adequacy of known proof techniques
for resolving questions such as whether P = NP? My research investigates
the structural properties of sets in these classes and explores
in a formal way the types of proof techniques necessary to resolve
problems concerning complexity classes. <P>

My research interests in computational biology are primarily in
the area of computational methods for genome sequencing. These
included the development of dynamic data structures and algorithms
for fragment assembly in large scale genome sequencing projects,
and the development of specific algorithmic techniques for handling
repetitive sequences. In addition my research has utilized graph
theoretic methods for doing rapid homology detection in the analysis
of anonymous sequences. <P>

<H2> Sample Recent Publications </H2>

Collapsing degrees in subexponential time (with R. Pruim and P.
Young), <EM>Proceedings of the Ninth Structure in Complexity Theory
Conference</EM>, 1994. <P>
 
On sparse spanners of weighted graphs (with I. Althofer, G. Das,
D. Dobkin, and Soares), <EM>Discrete and Computational Geometry</EM>,
vol. 9, 1993. <P>
 
Obtaining global similarity from local similarity (with J. Meidanis
and P. Tiwari), in <EM>Proceedings of the Fourth Scandinavian
Workshop on Algorithms</EM>, Springer-Verlag Lecture Notes in
Computer Science, vol. 621, pp. 326-337, 1992. <P>
 
<HR>
<ADDRESS>
 This page was automatically created October 30, 1995.<BR>
 Email <!WA2><A HREF="mailto:pubs@cs.wisc.edu">pubs@cs.wisc.edu</A>
to report errors.
</ADDRESS>
<HR>

</BODY>
</HTML>
